﻿// 0903train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
定义当一个字符串只有元音字母(a,e,i,o,u,A,E,I,O,U)组成,称为元音字符串，
现给定一个字符串，请找出其中最长的元音字符串，并返回其长度，如果找不到请返回0
字符串中任意一个连续字符组成的子序列称为该字符串的子串

输入
一个字符串s。字符串长度满足0 < len(s) < 10^5，字符串仅由字符a-z或A-Z组成
输出描述
一个整数，表示最长的元音字符子串的长度

输入
asdbuiodevauufgh
输出
3

最长的元音字符子串为uio和auu长度都为3，因此输出3
 */
class Solution01
{
public:
    Solution01(string&origin_str)
    {
        int result = 0;
        unordered_set<char>target_set;
        string target_str = "a,e,i,o,u,A,E,I,O,U";
        stringstream oh_sstream(target_str);
        string token;

        while (getline(oh_sstream,token, ','))
        {
            target_set.insert(token[0]);
        }

        for (int left =0; left <origin_str.size(); left++)
        {
            char curr_char = origin_str[left];
            if (target_set.count(curr_char)>0)
            {
                int length = 1;
                for (int right=left+1; right<origin_str.size();right++)
                {
                    char next_char = origin_str[right];
                    if (target_set.count(next_char)==0)
                    {
                        result = max(result, length);
                        break;
                    }
                	length++;
                }
            }

        }
        cout << result;
        //Solution01
    }
};


/*
 同一个数轴X上有两个点的集合A = {A1, A2, …, Am}和B = {B1, B2, …, Bn}
 Ai和Bj均为正整数，A、B已经按照从小到大排好序
A、B均不为空，给定一个距离R(正整数)，列出同时满足如下条件的所有(Ai, Bj)数：
1. Ai <= Bj
2. Ai, Bj之间的距离小于等于R
3. 在满足条件1和2的情况下，每个Ai只需输出距离最近的Bj
4. 输出结果按Ai从小到大的顺序排序

输入描述
第一行三个正整数m，n，R
第二行m个正整数，表示集合A
第三行n个正整数，表示集合B

输出描述
每组数对输出一行Ai和Bj，以空格隔开

输入
4 5 5
1 5 5 10
1 3 8 8 20
输出
1 1
5 8
5 8

输入
4 5 5 4m，5n，5R 集合A4 集合B5 Ai,Bj距离<=5
1 5 5 10 每个Ai只需输出距离最近的Bj
1 3 8 8 20
 */
class Solution02
{
public:
    Solution02(vector<int>&a_vec, vector<int>&b_vec, int distance)
    {
        //1. Ai <= Bj
        //2. Ai, Bj之间的距离小于等于R
        vector<vector<int>>result;

        int i = 0, j = 0;
        //双指针，因为两个数组都是排好序的
        //所以j不需要重置，前面的j都比当前i小，肯定也比i+1小
        while (i<a_vec.size())
        {
            int ai = a_vec[i];

            while (j<b_vec.size() && b_vec[j]<ai)
            {
                j++;
            }
            //退出循环以后，如果j<b_vec.size()，肯定存在ai<=bj
            if (j<b_vec.size() && b_vec[j]-ai<=distance)
            {
                vector<int>min_vec = { ai, b_vec[j] };
                result.push_back(min_vec);
            }
            i++;
        }

        //输出结果按Ai从小到大的顺序排序
        sort(result.begin(), result.end(), [](vector<int>&a, vector<int>&b)
            {
                return a[0] < b[0];
            });

        for (auto&min_vec:result)
        {
            cout << min_vec[0] << ' ' << min_vec[1] << endl;
        }

        //Solution02
    }
};

/*
 假设房子的总格数是count，小红每回合可能连续跳的步数都放在数据steps中，
 请问数组中是否有一种步数的组合，可以让小红三个回合跳到最后一格？
 如果有，请输出索引和最小的步数组合，数据保证索引和最小的步数组合是唯一的

 输入描述
第一行输入为每回合可能连续跳过的步数，它是整数数组类型
第二行输入为房子总格数count，它是整数类型int

输出描述
返回索引和最小满足要求的步数组合
注意：顺序保持steps中的原有顺序

1,4,5,2,0,2
9
输出
4,5,0
 */
class Solution03
{
public:
    Solution03(vector<int>&num_vec, int target)
    {
        vector<vector<int>>sort_vec;

        for (int i=0; i<num_vec.size(); i++)
        {
            vector<int>min_vec = { num_vec[i], i };
            sort_vec.push_back(min_vec);
        }

        sort(sort_vec.begin(), sort_vec.end(), [](vector<int>&a, vector<int>&b)
        {
        	if (a[0]==b[0])
        	{
                return a[1] < b[1];
        	}
            return a[0] < b[0];
        });

        int min_index_sum = INT_MAX;

        vector<vector<int>>result;

        for (int i=0; i< sort_vec.size(); i++)
        {
            int remain = target - sort_vec[i][0];

            int left = i + 1, right = sort_vec.size() - 1;
            while (left<right)
            {
                int sum = sort_vec[left][0] + sort_vec[right][0];
                if (sum<remain)
                {
                    left++;
                }
                else if (sum>remain)
                {
                    right--;
                }
                else
                {
                    int curr_i_sum = sort_vec[i][1] + sort_vec[left][1] + sort_vec[right][1];
                    if (curr_i_sum< min_index_sum)
                    {
                        result.clear();
                        result.push_back(sort_vec[i]);
                        result.push_back(sort_vec[left]);
                        result.push_back(sort_vec[right]);
                        min_index_sum = curr_i_sum;
                    }

                    right--;
                }

            }

        }

        sort(result.begin(), result.end(), [](vector<int>&a, vector<int>&b)
        {
            //按照索引排序
        	return a[1] < b[1];
        });

        for (int i=0; i< result.size(); i++)
        {
            cout << result[i][0];
            if (i!=result.size()-1)
            {
                cout << ',';
            }
        }

        //Solution03
    }
};

int main()
{
	{
        //-1,2,4,9
        //12
        //1,3,5,2,0,2,5
        //10

        vector<int>num_vec;
        string input = "1,3,5,2,0,2,5";
        int target = 10;
        //string input;
        //getline(cin, input);
        stringstream oh_sstream(input);
        string token;

        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        //int target;
        //cin >> target;

        Solution03 solu(num_vec, target);

        return 0;
	}
	{
/*
4 5 5
1 5 5 10
1 3 8 8 20
*/
        int a_size, b_size, distance;
        cin >> a_size >> b_size >> distance;

        vector<int>a_vec(a_size);
        vector<int>b_vec(b_size);

        for (int i=0; i<a_size; i++)
        {
            cin >> a_vec[i];
        }

        for (int i = 0; i < b_size; i++)
        {
            cin >> b_vec[i];
        }

        Solution02 solu(a_vec, b_vec, distance);

        return 0;
	}
    //string origin_str = "asdbuiodevauufgh";
    string origin_str;
    cin >> origin_str;
    Solution01 solu(origin_str);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
